

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=&#34;auto&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon%2032x32.ico">
  <link rel="icon" href="/img/favicon%2032x32.ico">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
    <meta http-equiv="Content-Security-Policy" content="upgrade-insecure-requests">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="">
  <meta name="author" content="hypocrite30">
  <meta name="keywords" content="">
  
  <title>Java常用集合源码分析 Ⅰ - hypocrite30</title>

  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap@4.5.3/dist/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/github-markdown-css@4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/lib/hint/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@10.4.0/styles/idea.min.css" />
    
  

  
    <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css" />
  



<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_ba1fz6golrf.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_kmeydafke9r.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script id="fluid-configs">
    var Fluid = window.Fluid || {};
    var CONFIG = {"hostname":"hypocrite30.gitee.io","root":"/","version":"1.8.9","typing":{"enable":true,"typeSpeed":70,"cursorChar":"_","loop":false},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"right","visible":"hover","icon":"§"},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"copy_btn":true,"image_zoom":{"enable":true},"toc":{"enable":true,"headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":2},"lazyload":{"enable":true,"loading_img":"/img/loading.gif","onlypost":false,"offset_factor":2},"web_analytics":{"enable":false,"baidu":"b5f391eebc7eaea88e68a49d5924e381","google":null,"gtag":null,"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null}}};
  </script>
  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.3.0"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>Hypocrite30 BLOG</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/links/">
                <i class="iconfont icon-link-fill"></i>
                友链
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner" id="banner" parallax=true
         style="background: url('/img/postPage.jpg') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="page-header text-center fade-in-up">
            <span class="h2" id="subtitle" title="Java常用集合源码分析 Ⅰ">
              
            </span>

            
              <div class="mt-3">
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2021-08-10 23:00" pubdate>
        2021年8月10日 晚上
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      6.1k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      105
       分钟
    </span>
  

  
  
    
      <!-- 不蒜子统计文章PV -->
      <span id="busuanzi_container_page_pv" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="busuanzi_value_page_pv"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid nopadding-x">
  <div class="row nomargin-x">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-x-md">
      <div class="container nopadding-x-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto">
            <!-- SEO header -->
            <h1 style="display: none">Java常用集合源码分析 Ⅰ</h1>
            
              <p class="note note-info">
                
                  本文最后更新于：2021年8月10日 晚上
                
              </p>
            
            <div class="markdown-body">
              <h1 id="Java常用集合源码分析-Ⅰ"><a href="#Java常用集合源码分析-Ⅰ" class="headerlink" title="Java常用集合源码分析 Ⅰ"></a>Java常用集合源码分析 Ⅰ</h1><blockquote>
<p>@Version: JDK 1.8</p>
<p>@IDE: IntellJ IDEA 2021.1</p>
<p>@Date: 2021/8/7 </p>
<p>@Author: Hypocrite30</p>
</blockquote>
<h2 id="一、集合"><a href="#一、集合" class="headerlink" title="一、集合"></a>一、集合</h2><ul>
<li>集合主要分为两大类：<code>Collection</code> &amp; <code>Map</code> </li>
</ul>
<p><img src="https://gitee.com/hypocrite30/ImgBed/raw/master/img/JavaCommons/image-20210807224135029.png" srcset="/img/loading.gif" lazyload></p>
<p><img src="https://gitee.com/hypocrite30/ImgBed/raw/master/img/JavaCommons/image-20210807224413506.png" srcset="/img/loading.gif" lazyload></p>
<h3 id="Ⅰ、Collection接口"><a href="#Ⅰ、Collection接口" class="headerlink" title="Ⅰ、Collection接口"></a>Ⅰ、Collection接口</h3><ul>
<li>有些实现类有序「List」，有些无序「Set」</li>
<li>有些可放重复元素，有些不可以</li>
<li>Collection 接口没有直接的实现子类，通过子接口「Set」「List」实现</li>
</ul>
<h3 id="Ⅱ、Iterator接口"><a href="#Ⅱ、Iterator接口" class="headerlink" title="Ⅱ、Iterator接口"></a>Ⅱ、Iterator接口</h3><ul>
<li>因为<code>Collection&lt;E&gt; extends Iterable&lt;E&gt;</code> ，所以所有子类都可以通过获取 <code>Iterator</code> 遍历集合</li>
</ul>
<p>常见方法：</p>
<table>
<thead>
<tr>
<th align="center">boolean</th>
<th>hashNext()</th>
<th>Returns: true if the iteration has more elements</th>
</tr>
</thead>
<tbody><tr>
<td align="center"><b>E</b></td>
<td><b>next()</b></td>
<td><b>Returns: the next element in the iteration</b></td>
</tr>
<tr>
<td align="center"><b>void</b></td>
<td><b>remove()</b></td>
<td><b>Removes from the underlying collection the last element returned by this iterator</b></td>
</tr>
</tbody></table>
<p>📌：在调用 <code>iterator.next()</code> 之前必须调用 <code>iterator.hasNext()</code> 判断后面是否存在元素。若不调用，到最后一个元素，调用 <code>next()</code> 会抛出 <code>NoSuchElementException</code></p>
<h3 id="Ⅲ、List接口"><a href="#Ⅲ、List接口" class="headerlink" title="Ⅲ、List接口"></a>Ⅲ、List接口</h3><ul>
<li>元素有序</li>
<li>可重复</li>
<li>支持索引</li>
<li>每个元素有一个整数型序号，记录元素在容器中的位置，可用于存取</li>
</ul>
<h2 id="二、ArrayList"><a href="#二、ArrayList" class="headerlink" title="二、ArrayList"></a>二、ArrayList</h2><ul>
<li><code>ArrayList</code> 可以存放任何数据，包括 <code>null</code></li>
<li><code>ArrayList</code> 基本等同于 <code>Vector</code>，区别在于前者是<strong>线程不安全</strong>的「执行效率高」</li>
<li><code>ArrayList</code> 内部存储数据结构为<strong>数组</strong></li>
</ul>
<h3 id="Ⅰ、Field"><a href="#Ⅰ、Field" class="headerlink" title="Ⅰ、Field"></a>Ⅰ、Field</h3><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">/**</span><br><span class="hljs-comment"> * 默认初始化容量</span><br><span class="hljs-comment"> */</span><br><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> DEFAULT_CAPACITY = <span class="hljs-number">10</span>;<br><br><span class="hljs-comment">/**</span><br><span class="hljs-comment"> * 空数组容量为0，有参构造默认使用的存储数据结构</span><br><span class="hljs-comment"> */</span><br><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> Object[] EMPTY_ELEMENTDATA = &#123;&#125;;<br><br><span class="hljs-comment">/**</span><br><span class="hljs-comment"> * 空数组容量为0，无参构造时默认使用的存储数据结构</span><br><span class="hljs-comment"> */</span><br><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = &#123;&#125;;<br><br><span class="hljs-comment">/**</span><br><span class="hljs-comment"> * 这ArrayList底层用到的存取数据的数组</span><br><span class="hljs-comment"> * 非私有，以简化嵌套类访问</span><br><span class="hljs-comment"> * transient 不允许序列化</span><br><span class="hljs-comment"> */</span><br><span class="hljs-keyword">transient</span> Object[] elementData;<br><br><span class="hljs-comment">/**</span><br><span class="hljs-comment"> * 实际ArrayList集合大小</span><br><span class="hljs-comment"> */</span><br><span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> size;<br><br><span class="hljs-comment">/**</span><br><span class="hljs-comment"> * 可分配的最大容量</span><br><span class="hljs-comment"> */</span><br><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> MAX_ARRAY_SIZE = Integer.MAX_VALUE - <span class="hljs-number">8</span>;<br></code></pre></div></td></tr></table></figure>
<p>📌几点说明：</p>
<ul>
<li>无参构造，数组默认初始化容量是 <strong>10</strong></li>
<li>预先创建好两个空数组，在构造过程中，直接赋值给存储数组</li>
<li>真正存储数据的数组是 <code>Object[] elementData</code>，并且被 <code>transient</code> 修饰，这样序列化不会将其写入流中，但是这样反序列化会丢失数据，需要分析 <code>writeObject(ObjectOutputStream s)</code> 和 <code>readObject(ObjectInputStream s)</code> 得到[序列化如何实现](#ArrayList 序列化与反序列化)</li>
<li>注意到 <code>MAX_ARRAY_SIZE</code> 数组最大长度是 <code>Integer.MAX_VALUE - 8</code>，[下面说明](#MAX_ARRAY_SIZE 数值说明)</li>
</ul>
<h4 id="ArrayList-序列化与反序列化"><a href="#ArrayList-序列化与反序列化" class="headerlink" title="ArrayList 序列化与反序列化"></a>ArrayList 序列化与反序列化</h4><ul>
<li><code>private void writeObject(java.io.ObjectOutputStream s)</code> 序列化<ul>
<li>序列化写入到流中有：<code>size</code> &amp; <code>element元素值</code> </li>
<li><code>elementData[]</code> 只做缓存数组，通常会预留容量，不够才扩容，因此序列化只取数组中需要的元素，<strong>节省空间和时间</strong>。</li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">writeObject</span><span class="hljs-params">(java.io.ObjectOutputStream s)</span></span><br><span class="hljs-function">    <span class="hljs-keyword">throws</span> java.io.IOException</span>&#123;<br>    <span class="hljs-comment">// 预期的修改次数，用于判断并发修改的问题</span><br>    <span class="hljs-keyword">int</span> expectedModCount = modCount;<br>    s.defaultWriteObject();<br><br>    <span class="hljs-comment">// 写入 ArrayList size</span><br>    s.writeInt(size);<br><br>    <span class="hljs-comment">// 写入每一个元素值</span><br>    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; size; i++) &#123;<br>        s.writeObject(elementData[i]);<br>    &#125;<br>	<span class="hljs-comment">// 判断序列化的并发问题</span><br>    <span class="hljs-keyword">if</span> (modCount != expectedModCount) &#123;<br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> ConcurrentModificationException();<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li><code>private void readObject(java.io.ObjectInputStream s)</code> 反序列化<ul>
<li>因为构造此 <code>ArrayList</code> 已经有模板和数据「序列化保存的size&amp;element」所以使用 <code>EMPTY_ELEMENTDATA</code> 作为空数组，而不是 <code>DEFAULTCAPACITY_EMPTY_ELEMENTDATA</code></li>
<li>根据 <code>size</code> 读入元素数据</li>
<li>按序列化正确顺序存入存储数组中</li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">readObject</span><span class="hljs-params">(java.io.ObjectInputStream s)</span></span><br><span class="hljs-function">    <span class="hljs-keyword">throws</span> java.io.IOException, ClassNotFoundException </span>&#123;<br>    <span class="hljs-comment">// 这里的 EMPTY_ELEMENTDATA 就是字段中的用于给有参构造用的空数组</span><br>    elementData = EMPTY_ELEMENTDATA;<br><br>    <span class="hljs-comment">// 按照 size 读入数据</span><br>    s.defaultReadObject();<br><br>    <span class="hljs-comment">// 读取容量</span><br>    s.readInt(); <span class="hljs-comment">// ignored</span><br><br>    <span class="hljs-keyword">if</span> (size &gt; <span class="hljs-number">0</span>) &#123;<br>        <span class="hljs-comment">// 与 clone() 类似，根据大小而不是容量分配阵列</span><br>        <span class="hljs-keyword">int</span> capacity = calculateCapacity(elementData, size);<br>        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);<br>        ensureCapacityInternal(size);<br><br>        Object[] a = elementData;<br>        <span class="hljs-comment">// 按正确顺序读入所有元素</span><br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; size; i++) &#123;<br>            a[i] = s.readObject();<br>        &#125;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="MAX-ARRAY-SIZE-数值说明"><a href="#MAX-ARRAY-SIZE-数值说明" class="headerlink" title="MAX_ARRAY_SIZE 数值说明"></a>MAX_ARRAY_SIZE 数值说明</h4><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">/**</span><br><span class="hljs-comment"> * The maximum size of array to allocate.</span><br><span class="hljs-comment"> * Some VMs reserve some header words in an array.</span><br><span class="hljs-comment"> * Attempts to allocate larger arrays may result in</span><br><span class="hljs-comment"> * OutOfMemoryError: Requested array size exceeds VM limit</span><br><span class="hljs-comment"> */</span><br><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> MAX_ARRAY_SIZE = Integer.MAX_VALUE - <span class="hljs-number">8</span>;<br></code></pre></div></td></tr></table></figure>
<p>官方注释解释，有些虚拟机会保留一些字段空间，如果用满 <code>Integer.MAX_VALUE</code> <strong>可能</strong>会 OOM。</p>
<p>StackOverflow 上的部分解释提及到「内存模型里的<strong>对象头</strong>的组成」<sup id="fnref:1" class="footnote-ref"><a href="#fn:1" rel="footnote">&lt;span class=”hint–top hint–rounded” aria-label=”Why the maximum array size of ArrayList is Integer.MAX_VALUE - 8?</p>
<p>“&gt;[1]</span></a></sup></p>
<p>于是对于 <strong>Java数组对象</strong> 剖析<sup id="fnref:2" class="footnote-ref"><a href="#fn:2" rel="footnote">&lt;span class=”hint–top hint–rounded” aria-label=”Anatomy of a Java array object</p>
<p>“&gt;[2]</span></a></sup></p>
<p>IBM官方说到「与Java对象相比，区别在于数组对象有一个额外的元数据，用于表示 <strong>数组的大小</strong>」</p>
<p>剖析 <strong>Java对象</strong>  <sup id="fnref:3" class="footnote-ref"><a href="#fn:3" rel="footnote">&lt;span class=”hint–top hint–rounded” aria-label=”Anatomy of a Java object</p>
<p>“&gt;[3]</span></a></sup></p>
<p>不同的JVM厂商对元数据数量的设计有差异，但通常包括：</p>
<ul>
<li><strong>Class</strong>：指向类信息的指针，即类型指针。指向方法区中的类元信息。</li>
<li><strong>Flags</strong>：描述对象状态的标志集合，包括 hashcode 和 shape「对象是否为数组」</li>
<li><strong>Lock</strong>： 对象的同步信息「当前对象是否同步」</li>
</ul>
<p>而 <strong>Java数组对象</strong> 还多一个 <strong>Size</strong>，即数组的大小。</p>
<p>「<a target="_blank" rel="noopener" href="https://stackoverflow.com/questions/35756277/why-the-maximum-array-size-of-arraylist-is-integer-max-value-8#:~:text=The%20size%20of%20object%20header%20can%20not%20exceed%208%20byte.">对象头的大小不能超过 8 字节</a>」</p>
<p><strong>标记字 Mark Word</strong>「哈希值、GC分代年龄、锁状态标志、线程持有的锁、偏向线程ID、偏向时间戳」在 32 位架构占 4 byte，64 位架构占 8 byte；<strong>类型指针Klass pointer</strong> 在 32 为架构上具有字长，但如果堆地址可以用 4 byte 编码，则依然可以占 4 byte。</p>
<p>📌：所以为了保险起见「防止OOM」，最大数组长度设置为 <code>Integer.MAX_VALUE - 8</code> </p>
<h3 id="Ⅱ、Constructor"><a href="#Ⅱ、Constructor" class="headerlink" title="Ⅱ、Constructor"></a>Ⅱ、Constructor</h3><h4 id="无参构造"><a href="#无参构造" class="headerlink" title="无参构造"></a>无参构造</h4><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">/**</span><br><span class="hljs-comment"> * 构造一个初始容量为10的空列表</span><br><span class="hljs-comment"> */</span><br><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ArrayList</span><span class="hljs-params">()</span> </span>&#123;<br>    <span class="hljs-keyword">this</span>.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>这里的初始容量为 10，在字段 <code>DEFAULT_CAPACITY = 10</code> 体现出来的</li>
</ul>
<h4 id="有参构造"><a href="#有参构造" class="headerlink" title="有参构造"></a>有参构造</h4><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ArrayList</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (initialCapacity &gt; <span class="hljs-number">0</span>) &#123;<br>        <span class="hljs-keyword">this</span>.elementData = <span class="hljs-keyword">new</span> Object[initialCapacity];<br>    &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (initialCapacity == <span class="hljs-number">0</span>) &#123;<br>        <span class="hljs-keyword">this</span>.elementData = EMPTY_ELEMENTDATA;<br>    &#125; <span class="hljs-keyword">else</span> &#123;<br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException(<span class="hljs-string">&quot;Illegal Capacity: &quot;</span>+<br>                                           initialCapacity);<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>构造一个具有指定初始容量的空列表</li>
<li>如果入参为负数，则抛出异常</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ArrayList</span><span class="hljs-params">(Collection&lt;? extends E&gt; c)</span> </span>&#123;<br>    <span class="hljs-comment">// 按正确顺序包含此列表中所有元素的数组</span><br>    Object[] a = c.toArray();<br>    <span class="hljs-comment">// 先更新 size 值，再判断。如果是空数组则直接使用默认空数组</span><br>    <span class="hljs-keyword">if</span> ((size = a.length) != <span class="hljs-number">0</span>) &#123;<br>        <span class="hljs-comment">// 判断 c 集合是不是ArrayList，是则直接赋值</span><br>        <span class="hljs-keyword">if</span> (c.getClass() == ArrayList.class) &#123;<br>            elementData = a;<br>        &#125; <span class="hljs-keyword">else</span> &#123; <span class="hljs-comment">// 否则手动拷贝一份 Object[]</span><br>            elementData = Arrays.copyOf(a, size, Object[].class);<br>        &#125;<br>    &#125; <span class="hljs-keyword">else</span> &#123;<br>        <span class="hljs-comment">// replace with empty array.</span><br>        elementData = EMPTY_ELEMENTDATA;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>按照集合迭代器返回的顺序，构造包含指定集合元素的列表。即传入一个集合类</li>
<li>传入 null 则抛出 <code>NullPointerException</code> </li>
</ul>
<h3 id="Ⅲ、Method"><a href="#Ⅲ、Method" class="headerlink" title="Ⅲ、Method"></a>Ⅲ、Method</h3><h4 id="增添元素-add-E-e"><a href="#增添元素-add-E-e" class="headerlink" title="增添元素 add(E e)"></a>增添元素 add(E e)</h4><ul>
<li>添加元素 e</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">add</span><span class="hljs-params">(E e)</span> </span>&#123;<br>    ensureCapacityInternal(size + <span class="hljs-number">1</span>);  <span class="hljs-comment">// Increments modCount!!</span><br>    elementData[size++] = e;<br>    <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li><p><code>ensureCapacityInternal(int minCapacity)</code> <a href="#%E6%89%A9%E5%AE%B9%E6%9C%BA%E5%88%B6">检查是否扩容</a>，确保容量<strong>至少</strong>达到 <code>size + 1</code>，在此过程中，modCount 会增加，因为扩容属于修改操作。</p>
</li>
<li><p>确保容量够后，将值存入数组「<strong>elementData</strong>」同时 <code>size ++</code></p>
</li>
</ul>
<h4 id="添加元素-add-int-index-E-element"><a href="#添加元素-add-int-index-E-element" class="headerlink" title="添加元素 add(int index, E element)"></a>添加元素 add(int index, E element)</h4><ul>
<li>在指定 index 位置插入元素，其后的元素都向右移动</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">add</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index, E element)</span> </span>&#123;<br>    rangeCheckForAdd(index);<br><br>    ensureCapacityInternal(size + <span class="hljs-number">1</span>);  <span class="hljs-comment">// Increments modCount!!</span><br>    System.arraycopy(elementData, index, elementData, index + <span class="hljs-number">1</span>,<br>                     size - index);<br>    elementData[index] = element;<br>    size++;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">rangeCheckForAdd</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (index &gt; size || index &lt; <span class="hljs-number">0</span>)<br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IndexOutOfBoundsException(outOfBoundsMsg(index));<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>先检查 index 的合法性</li>
<li><a href="#%E6%89%A9%E5%AE%B9%E6%9C%BA%E5%88%B6">检查是否扩容</a>，确保容量<strong>至少</strong>达到 <code>size + 1</code>，期间 modCount 增加</li>
<li>[index, size] 的元素向后移动一个单位</li>
<li>插入元素，更新 size 值</li>
</ul>
<h4 id="删除-remove-int-index"><a href="#删除-remove-int-index" class="headerlink" title="删除 remove(int index)"></a>删除 remove(int index)</h4><ul>
<li>删除下标为 index 的元素</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">remove</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;<br>    rangeCheck(index);<br><br>    modCount++;<br>    E oldValue = elementData(index);<br><br>    <span class="hljs-keyword">int</span> numMoved = size - index - <span class="hljs-number">1</span>;<br>    <span class="hljs-keyword">if</span> (numMoved &gt; <span class="hljs-number">0</span>)<br>        System.arraycopy(elementData, index + <span class="hljs-number">1</span>, elementData, index,<br>                         numMoved);<br>    elementData[--size] = <span class="hljs-keyword">null</span>; <span class="hljs-comment">// 方便 GC</span><br><br>    <span class="hljs-keyword">return</span> oldValue;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">// 上述使用到的方法实现</span><br><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">rangeCheck</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (index &gt;= size)<br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IndexOutOfBoundsException(outOfBoundsMsg(index));<br>&#125;<br><span class="hljs-function">E <span class="hljs-title">elementData</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;<br>    <span class="hljs-keyword">return</span> (E) elementData[index];<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>检查 index 合法性，修改计数器 modCount ++</li>
<li>获取旧元素，作为方法返回值</li>
<li>计算需要还原的后面的元素个数为 <code>size - index - 1</code></li>
<li>后面的元素全部向前移动一个单位，旧元素被<strong>覆盖</strong></li>
<li>删除操作前数组的最后一位置空，方便 GC</li>
</ul>
<h4 id="删除-remove-Object-o"><a href="#删除-remove-Object-o" class="headerlink" title="删除 remove(Object o)"></a>删除 remove(Object o)</h4><ul>
<li>删除指定元素 o</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">remove</span><span class="hljs-params">(Object o)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (o == <span class="hljs-keyword">null</span>) &#123;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>; index &lt; size; index++)<br>            <span class="hljs-keyword">if</span> (elementData[index] == <span class="hljs-keyword">null</span>) &#123;<br>                fastRemove(index);<br>                <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;<br>            &#125;<br>    &#125; <span class="hljs-keyword">else</span> &#123;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>; index &lt; size; index++)<br>            <span class="hljs-keyword">if</span> (o.equals(elementData[index])) &#123;<br>                fastRemove(index);<br>                <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;<br>            &#125;<br>    &#125;<br>    <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">// 没有返回值的 remove(int index)</span><br><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">fastRemove</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;<br>    modCount++;<br>    <span class="hljs-keyword">int</span> numMoved = size - index - <span class="hljs-number">1</span>;<br>    <span class="hljs-keyword">if</span> (numMoved &gt; <span class="hljs-number">0</span>)<br>        System.arraycopy(elementData, index+<span class="hljs-number">1</span>, elementData, index,<br>                         numMoved);<br>    elementData[--size] = <span class="hljs-keyword">null</span>; <span class="hljs-comment">// 方便 GC</span><br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>简单的 for - loop 找值，同时也能找到存储进去的 null 值「非扩容部分的 null」条件是 <code>index &lt; size</code> </li>
</ul>
<h4 id="删除-clear"><a href="#删除-clear" class="headerlink" title="删除 clear()"></a>删除 clear()</h4><ul>
<li>清空所有元素值</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">clear</span><span class="hljs-params">()</span> </span>&#123;<br>    modCount++;<br>    <span class="hljs-comment">// 方便 GC</span><br>    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; size; i++)<br>        elementData[i] = <span class="hljs-keyword">null</span>;<br>    size = <span class="hljs-number">0</span>;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>修改计数器自增；元素置空，便于GC；最后修改 size</li>
</ul>
<h4 id="修改-set-int-index-E-element"><a href="#修改-set-int-index-E-element" class="headerlink" title="修改 set(int index, E element)"></a>修改 set(int index, E element)</h4><ul>
<li>将 index 位置的元素值修改为 element</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">set</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index, E element)</span> </span>&#123;<br>    rangeCheck(index);<br><br>    E oldValue = elementData(index);<br>    elementData[index] = element;<br>    <span class="hljs-keyword">return</span> oldValue;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>先检查 index 的合法性</li>
<li>获取旧值；修改</li>
<li>返回旧值</li>
</ul>
<h4 id="查找-get-int-index"><a href="#查找-get-int-index" class="headerlink" title="查找 get(int index)"></a>查找 get(int index)</h4><ul>
<li>查找并返回 index 位置的值</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">get</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;<br>    rangeCheck(index);<br><br>    <span class="hljs-keyword">return</span> elementData(index);<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="扩容机制"><a href="#扩容机制" class="headerlink" title="扩容机制"></a>扩容机制</h4><ul>
<li>确保存储数组的容量<strong>至少</strong>达到 <code>minCapacity</code> 的大小</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">ensureCapacityInternal</span><span class="hljs-params">(<span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;<br>    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));<br>&#125;<br></code></pre></div></td></tr></table></figure>


<ul>
<li>计算<strong>预期</strong>数组容量<ul>
<li><code>elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA</code> 判断当前数组是不是<strong>无参构造</strong>创造出来的<strong>容量为0</strong>的数组</li>
<li>如果是，则计算出来的数组容量即为 <code>size + 1</code>，即 <code>0 + 1</code>，因为默认空数组size == 0</li>
<li>否则直接返回 minCapacity，即传进来的 [size + 1](#增添元素 add(E e))</li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> <span class="hljs-title">calculateCapacity</span><span class="hljs-params">(Object[] elementData, <span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) &#123;<br>        <span class="hljs-keyword">return</span> Math.max(DEFAULT_CAPACITY, minCapacity);<br>    &#125;<br>    <span class="hljs-keyword">return</span> minCapacity;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<p>📌Q：if 语句返回的一直都是 <code>minCapacity</code>「因为正数minCapacity &gt; DEFAULT_CAPACITY (0)」，而 if 语句外也是返回 <code>minCapacity</code>。设计意义在哪？</p>
<p>A：假设传入的 <code>minCapacity</code> 是负数，即 add() 中的 <code>size + 1</code> 仍为负数，则会返回 <code>DEFAULT_CAPACITY</code> AKA <strong>10</strong>，即无参构造默认创建容量为 <strong>10</strong> 的数组，所以这么设计可以解决非法入参。</p>
<p>Q：为什么要判断「elementData」是否是 默认空数组<code>DEFAULTCAPACITY_EMPTY_ELEMENTDATA</code></p>
<p>A：其实此 if 语句只有第一次扩容会使用到，真正的扩容 <code>grow()</code> 在每一次扩容都会创建出新的数组覆盖掉 <code>elementData</code>，扩容之后肯定就能确保入参 <code>minCapacity</code> 是正数（[size + 1](#增添元素 add(E e))），不需要再判断。</p>
<ul>
<li>确保明确的容量，做扩容前的最后一次确认<ul>
<li>修改计数器自增</li>
<li>判断刚才计算的<strong>预期</strong>数组容量 是否大于 当前数组容量</li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">ensureExplicitCapacity</span><span class="hljs-params">(<span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;<br>    modCount++;<br>    <span class="hljs-comment">// overflow-conscious code</span><br>    <span class="hljs-keyword">if</span> (minCapacity - elementData.length &gt; <span class="hljs-number">0</span>)<br>        grow(minCapacity);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<p>📌官方在条件判断这里注解了 溢出警告「overflow-conscious」，这里涉及到 <code>a &lt; b</code> 与 <code>a - b &lt; 0</code> 区别的问题，[下文说明](#关于 a &lt; b 与 a - b &lt; 0 应用说明)。</p>
<ul>
<li>扩容操作<ul>
<li>获取旧容量，根据旧容量的 <strong>1.5</strong> 倍大小作为新容量，使用<strong>位运算</strong>提高效率。</li>
<li>两个特殊判断后，进行扩容，使用的是 <code>Arrays.copyOf</code> 扩容，这会创建出<strong>新数组</strong>覆盖原数组</li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">grow</span><span class="hljs-params">(<span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;<br>    <span class="hljs-comment">// overflow-conscious code</span><br>    <span class="hljs-keyword">int</span> oldCapacity = elementData.length;<br>    <span class="hljs-keyword">int</span> newCapacity = oldCapacity + (oldCapacity &gt;&gt; <span class="hljs-number">1</span>); <span class="hljs-comment">// AKA 1.5倍扩容</span><br>    <span class="hljs-comment">// 只有第一次才会 true 修改新容量</span><br>    <span class="hljs-keyword">if</span> (newCapacity - minCapacity &lt; <span class="hljs-number">0</span>)<br>        newCapacity = minCapacity;<br>    <span class="hljs-comment">// 如果新容量太大，则按照大容量处理方式</span><br>    <span class="hljs-keyword">if</span> (newCapacity - MAX_ARRAY_SIZE &gt; <span class="hljs-number">0</span>)<br>        newCapacity = hugeCapacity(minCapacity);<br>    <span class="hljs-comment">// minCapacity is usually close to size, so this is a win:</span><br>    elementData = Arrays.copyOf(elementData, newCapacity);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<p>📌Q：第一个条件 <code>newCapacity &lt; minCapacity</code> 判断奇怪，新容量为什么会比预测容量小。预测容量是 <code>size + 1</code>，即所有数据长度 + 1，而新容量是在原容量基础上扩大 1.5 倍，肯定比 <code>minCapacity</code> 要大。</p>
<p>A：在无参构造创建空数组时，<code>oldCapacity</code> 原容量为 0，<strong>扩大 1.5 倍仍然为 0</strong>。此时新容量自然比预测容量要小，将值为0的 <code>newCapacity</code> 更新为 预测容量。而在此之后，这一更新操作都不会进行，因为扩容容量肯定比预测容量大「(x1.5) &gt; (+ 1)」。</p>
<ul>
<li>大容量处理方式<ul>
<li>int 型一直累加到负数，说明已经超出 int 存储的最大值了，抛异常</li>
<li>预测容量 &gt;  允许的最大容量，则让新容量为 int 最大值，否则为 <code>MAX_ARRAY_SIZE</code>，即 <code>Integer.MAX_VALUE - 8</code>，相当于给一个稳妥的值，[不至于OOM](#MAX_ARRAY_SIZE 数值说明)。</li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> <span class="hljs-title">hugeCapacity</span><span class="hljs-params">(<span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (minCapacity &lt; <span class="hljs-number">0</span>) <span class="hljs-comment">// overflow</span><br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> OutOfMemoryError();<br>    <span class="hljs-keyword">return</span> (minCapacity &gt; MAX_ARRAY_SIZE) ?<br>        Integer.MAX_VALUE :<br>        MAX_ARRAY_SIZE;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<ul>
<li>Arrays 工具类扩容<ul>
<li>最终都会调用本地方法 <code>arraycopy()</code> 进行扩容</li>
<li>可以看到，返回的 <code>copy</code> 数组都是 new 出来的，所以扩容会让存储数组变成不同对象</li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> &lt;T&gt; T[] copyOf(T[] original, <span class="hljs-keyword">int</span> newLength) &#123;<br>    <span class="hljs-keyword">return</span> (T[]) copyOf(original, newLength, original.getClass());<br>&#125;<br><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> &lt;T,U&gt; T[] copyOf(U[] original, <span class="hljs-keyword">int</span> newLength, Class&lt;? extends T[]&gt; newType) &#123;<br>    T[] copy = ((Object)newType == (Object)Object[].class)<br>        ? (T[]) <span class="hljs-keyword">new</span> Object[newLength]<br>        : (T[]) Array.newInstance(newType.getComponentType(), newLength);<br>    System.arraycopy(original, <span class="hljs-number">0</span>, copy, <span class="hljs-number">0</span>,<br>                     Math.min(original.length, newLength));<br>    <span class="hljs-keyword">return</span> copy;<br>&#125;<br><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">native</span> <span class="hljs-keyword">void</span> <span class="hljs-title">arraycopy</span><span class="hljs-params">(Object src,  <span class="hljs-keyword">int</span>  srcPos,</span></span><br><span class="hljs-function"><span class="hljs-params">                                        Object dest, <span class="hljs-keyword">int</span> destPos,</span></span><br><span class="hljs-function"><span class="hljs-params">                                        <span class="hljs-keyword">int</span> length)</span></span>;<br></code></pre></div></td></tr></table></figure>


<h3 id="关于-a-lt-b-与-a-b-lt-0-应用说明"><a href="#关于-a-lt-b-与-a-b-lt-0-应用说明" class="headerlink" title="关于 a &lt; b 与 a - b &lt; 0 应用说明"></a>关于 a &lt; b 与 a - b &lt; 0 应用说明</h3><p>Q：看到上述扩容的很多条件判断使用的都是 <code>a - b &lt; 0</code> 的形式，而不是直接比较，这种设计的好处在哪？</p>
<p>在数学中，这两个不等式是完全等价的。但在计算机中，需要考虑到存储的问题，有可能会出现变量 <code>a | b</code> 出现</p>
<p><strong>溢出</strong>的情况。</p>
<p>🌰Demo <sup id="fnref:4" class="footnote-ref"><a href="#fn:4" rel="footnote"><span class="hint--top hint--rounded" aria-label="[Difference between if (a - b &lt; 0) and if (a &lt; b)]
">[4]</span></a></sup>：</p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">int</span> a = Integer.MAX_VALUE;<br><span class="hljs-keyword">int</span> b = Integer.MIN_VALUE;<br><span class="hljs-keyword">if</span> (a &lt; b) System.out.println(<span class="hljs-string">&quot;a &lt; b&quot;</span>);<br><span class="hljs-keyword">if</span> (a - b &lt; <span class="hljs-number">0</span>) System.out.println(<span class="hljs-string">&quot;a - b &lt; 0&quot;</span>);<br></code></pre></div></td></tr></table></figure>
<blockquote>
<p>结果：a - b &lt; 0</p>
</blockquote>
<ul>
<li>正常情况下，a 肯定小于 b</li>
<li>但是结果是 <code>a - b &lt; 0</code> 为 true，即 a &lt; b</li>
</ul>
<p>分析：<code>a - b</code> 超出 int 存储最大范围，于是<strong>溢出</strong>，变成负数</p>
<p>ArrayList 前的判断：</p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">// overflow-conscious code</span><br><span class="hljs-keyword">if</span> (minCapacity - elementData.length &gt; <span class="hljs-number">0</span>)<br>    grow(minCapacity);<br></code></pre></div></td></tr></table></figure>
<p>官方也提出 溢出警告</p>
<ul>
<li><p>使用 <code>a &lt; b</code> 形式</p>
<ul>
<li>如果 <code>minCapacity</code> 过大，溢出变成负数，此时不会扩容，然而此情况是有扩容需求的</li>
</ul>
</li>
<li><p>使用 <code>a - b &lt; 0</code> 形式</p>
<ul>
<li>如果 <code>minCapacity</code> 过大，溢出为负数，而减去一个正数又会回到正数，此时就会顺利进入扩容中</li>
</ul>
</li>
</ul>
<p><code>grow()</code> :</p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">// overflow-conscious code</span><br><span class="hljs-keyword">int</span> oldCapacity = elementData.length;<br><span class="hljs-keyword">int</span> newCapacity = oldCapacity + (oldCapacity &gt;&gt; <span class="hljs-number">1</span>);<br><span class="hljs-keyword">if</span> (newCapacity - minCapacity &lt; <span class="hljs-number">0</span>)<br>    newCapacity = minCapacity;<br><span class="hljs-keyword">if</span> (newCapacity - MAX_ARRAY_SIZE &gt; <span class="hljs-number">0</span>)<br>    newCapacity = hugeCapacity(minCapacity);<br></code></pre></div></td></tr></table></figure>
<p>同样也有溢出警告</p>
<ul>
<li>使用 <code>a &lt; b</code> 形式<ul>
<li><code>newCapacity</code> 如果扩容 1.5 倍后太大溢出为负数，则会小于 <code>minCapacity</code>，会更新 <code>newCapacity = minCapacity;</code> </li>
<li>下一个条件判断，<code>newCapacity</code> 为负数 会小于 <code>MAX_ARRAY_SIZE</code>，所以不会进行 超大容量处理，则会出现问题</li>
</ul>
</li>
<li>使用 <code>a - b &lt; 0</code> 形式<ul>
<li>第一个条件判断，溢出为负数的 <code>newCapacity</code>，减去正数 <code>minCapacity</code> 结果大于 0，不更新 <code>newCapacity</code>，即只有第一次扩容「空数组」会更新</li>
<li>第二个条件判断，同理，会执行超大容量处理，合乎逻辑。</li>
</ul>
</li>
</ul>
<h2 id="三、Vector"><a href="#三、Vector" class="headerlink" title="三、Vector"></a>三、Vector</h2><ul>
<li>因为方法上加了 <code>synchronized</code>，是方法级的锁，所以是线程安全的。</li>
<li>大部分逻辑和设计与 <code>ArrayList</code> 相同</li>
</ul>
<h3 id="Ⅰ、Field-1"><a href="#Ⅰ、Field-1" class="headerlink" title="Ⅰ、Field"></a>Ⅰ、Field</h3><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">// 存储数组</span><br><span class="hljs-keyword">protected</span> Object[] elementData;<br><span class="hljs-comment">// 真实元素的数量</span><br><span class="hljs-keyword">protected</span> <span class="hljs-keyword">int</span> elementCount;<br><span class="hljs-comment">// 扩容因子，详细作用见扩容函数</span><br><span class="hljs-keyword">protected</span> <span class="hljs-keyword">int</span> capacityIncrement;<br></code></pre></div></td></tr></table></figure>


<h3 id="Ⅱ、Constructor-1"><a href="#Ⅱ、Constructor-1" class="headerlink" title="Ⅱ、Constructor"></a>Ⅱ、Constructor</h3><h4 id="无参构造-1"><a href="#无参构造-1" class="headerlink" title="无参构造"></a>无参构造</h4><ul>
<li>无参构造默认的数组长度是 <strong>10</strong></li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Vector</span><span class="hljs-params">()</span> </span>&#123;<br>    <span class="hljs-keyword">this</span>(<span class="hljs-number">10</span>);<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="有参构造-1"><a href="#有参构造-1" class="headerlink" title="有参构造"></a>有参构造</h4><ul>
<li>自定义数组长度，默认的扩容因子是 <strong>0</strong>，即扩容是 <strong>2</strong> 倍扩容</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Vector</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity)</span> </span>&#123;<br>    <span class="hljs-keyword">this</span>(initialCapacity, <span class="hljs-number">0</span>);<br>&#125;<br></code></pre></div></td></tr></table></figure>


<ul>
<li>自定义数组长度 &amp; 扩容因子</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Vector</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity, <span class="hljs-keyword">int</span> capacityIncrement)</span> </span>&#123;<br>    <span class="hljs-keyword">super</span>();<br>    <span class="hljs-keyword">if</span> (initialCapacity &lt; <span class="hljs-number">0</span>)<br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException(<span class="hljs-string">&quot;Illegal Capacity: &quot;</span>+<br>                                           initialCapacity);<br>    <span class="hljs-keyword">this</span>.elementData = <span class="hljs-keyword">new</span> Object[initialCapacity];<br>    <span class="hljs-keyword">this</span>.capacityIncrement = capacityIncrement;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<ul>
<li>按照传入的集合初始化</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Vector</span><span class="hljs-params">(Collection&lt;? extends E&gt; c)</span> </span>&#123;<br>    Object[] a = c.toArray();<br>    elementCount = a.length;<br>    <span class="hljs-keyword">if</span> (c.getClass() == ArrayList.class) &#123;<br>        elementData = a;<br>    &#125; <span class="hljs-keyword">else</span> &#123;<br>        elementData = Arrays.copyOf(a, elementCount, Object[].class);<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h3 id="Ⅲ、Method-1"><a href="#Ⅲ、Method-1" class="headerlink" title="Ⅲ、Method"></a>Ⅲ、Method</h3><ul>
<li>大部分方法都与 <code>ArrayList</code> 相同</li>
</ul>
<h4 id="扩容机制-1"><a href="#扩容机制-1" class="headerlink" title="扩容机制"></a>扩容机制</h4><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">synchronized</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">add</span><span class="hljs-params">(E e)</span> </span>&#123;<br>    modCount++;<br>    ensureCapacityHelper(elementCount + <span class="hljs-number">1</span>);<br>    elementData[elementCount++] = e;<br>    <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>扩容前的检查</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">ensureCapacityHelper</span><span class="hljs-params">(<span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;<br>    <span class="hljs-comment">// overflow-conscious code</span><br>    <span class="hljs-keyword">if</span> (minCapacity - elementData.length &gt; <span class="hljs-number">0</span>)<br>        grow(minCapacity);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>📌扩容</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">grow</span><span class="hljs-params">(<span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;<br>    <span class="hljs-comment">// overflow-conscious code</span><br>    <span class="hljs-keyword">int</span> oldCapacity = elementData.length;<br>    <span class="hljs-keyword">int</span> newCapacity = oldCapacity + ((capacityIncrement &gt; <span class="hljs-number">0</span>) ?<br>                                     capacityIncrement : oldCapacity); <span class="hljs-comment">// 扩容机制</span><br>    <span class="hljs-keyword">if</span> (newCapacity - minCapacity &lt; <span class="hljs-number">0</span>)<br>        newCapacity = minCapacity;<br>    <span class="hljs-keyword">if</span> (newCapacity - MAX_ARRAY_SIZE &gt; <span class="hljs-number">0</span>)<br>        newCapacity = hugeCapacity(minCapacity);<br>    elementData = Arrays.copyOf(elementData, newCapacity);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<p><code>newCapacity</code> 是旧容量 加上一个值，三目运算符判断扩容因子是多少，如果是默认的 0 或者小于 0，则扩容两倍。</p>
<p>否则扩容 <code>1 + capacityIncrement</code> 倍</p>
<h2 id="四、LinkedList"><a href="#四、LinkedList" class="headerlink" title="四、LinkedList"></a>四、LinkedList</h2><ul>
<li>使用的数据结构是 <strong>双向链表</strong></li>
<li>继承了 <code>List</code> 和 <code>Deque</code>，所以可以当成列表集合 和 双端队列</li>
<li> 非线程安全；使之线程安全的办法是调用 <code>Collections</code> 工具类的 <code>synchronizedList(List&lt;T&gt; list)</code> 方法转化成线程安全的集合</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java">List list = Collections.synchronizedList(<span class="hljs-keyword">new</span> LinkedList(...));<br></code></pre></div></td></tr></table></figure>


<h3 id="Ⅰ、Field-2"><a href="#Ⅰ、Field-2" class="headerlink" title="Ⅰ、Field"></a>Ⅰ、Field</h3><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">// 节点（元素）个数</span><br><span class="hljs-keyword">transient</span> <span class="hljs-keyword">int</span> size = <span class="hljs-number">0</span>;<br><span class="hljs-comment">// 指向第一个节点的指针。</span><br><span class="hljs-keyword">transient</span> Node&lt;E&gt; first;<br><span class="hljs-comment">// 指向末尾节点</span><br><span class="hljs-keyword">transient</span> Node&lt;E&gt; last;<br></code></pre></div></td></tr></table></figure>
<p>根据双向链表储存特点</p>
<p>在运行中的不变量：</p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java">(first == <span class="hljs-keyword">null</span> &amp;&amp; last == <span class="hljs-keyword">null</span>) || (first.prev == <span class="hljs-keyword">null</span> &amp;&amp; first.item != <span class="hljs-keyword">null</span>)<br>(first == <span class="hljs-keyword">null</span> &amp;&amp; last == <span class="hljs-keyword">null</span>) || (last.next == <span class="hljs-keyword">null</span> &amp;&amp; last.item != <span class="hljs-keyword">null</span>)<br></code></pre></div></td></tr></table></figure>


<h4 id="静态内部类"><a href="#静态内部类" class="headerlink" title="静态内部类"></a>静态内部类</h4><p><img src="https://gitee.com/hypocrite30/ImgBed/raw/master/img/JavaCommons/1628515716530-screenshot.png" srcset="/img/loading.gif" lazyload></p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Node</span>&lt;<span class="hljs-title">E</span>&gt; </span>&#123;<br>    E item;<br>    Node&lt;E&gt; next;<br>    Node&lt;E&gt; prev;<br><br>    Node(Node&lt;E&gt; prev, E element, Node&lt;E&gt; next) &#123;<br>        <span class="hljs-keyword">this</span>.item = element;<br>        <span class="hljs-keyword">this</span>.next = next;<br>        <span class="hljs-keyword">this</span>.prev = prev;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>由此可看出底层数据结构是 <strong>双向链表</strong></li>
</ul>
<h3 id="Ⅱ、Constructor-2"><a href="#Ⅱ、Constructor-2" class="headerlink" title="Ⅱ、Constructor"></a>Ⅱ、Constructor</h3><h4 id="无参构造-2"><a href="#无参构造-2" class="headerlink" title="无参构造"></a>无参构造</h4><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">// Constructs an empty list.</span><br><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">LinkedList</span><span class="hljs-params">()</span> </span>&#123;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="有参构造-2"><a href="#有参构造-2" class="headerlink" title="有参构造"></a>有参构造</h4><ul>
<li>将入参集合元素添加进新的 <code>LinkedList</code> 集合</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">LinkedList</span><span class="hljs-params">(Collection&lt;? extends E&gt; c)</span> </span>&#123;<br>    <span class="hljs-keyword">this</span>();<br>    addAll(c);<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h3 id="Ⅲ、Method-2"><a href="#Ⅲ、Method-2" class="headerlink" title="Ⅲ、Method"></a>Ⅲ、Method</h3><h4 id="添加-add-E-e"><a href="#添加-add-E-e" class="headerlink" title="添加 add(E e)"></a>添加 add(E e)</h4><ul>
<li>添加元素，使用[尾插法](#尾插法添加元素 linkLast(E e))</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">add</span><span class="hljs-params">(E e)</span> </span>&#123;<br>    linkLast(e);<br>    <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="添加-add-int-index-E-element"><a href="#添加-add-int-index-E-element" class="headerlink" title="添加 add(int index, E element)"></a>添加 add(int index, E element)</h4><ul>
<li>添加元素到指定下标位置<ul>
<li>检查下标合法性</li>
<li>判断插入位置是在末尾「[尾插](#尾插法添加元素 linkLast(E e))」还是在「[插入非空节点之前](#插入元素到非空节点之前 linkBefore(E e, Node<E> succ))」</li>
<li>「插入非空节点之前」用到 [node(int index)](#检索节点在链表的下标位置 node(int index)) 计算返回下标位置节点</li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">add</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index, E element)</span> </span>&#123;<br>    checkPositionIndex(index);<br><br>    <span class="hljs-keyword">if</span> (index == size)<br>        linkLast(element);<br>    <span class="hljs-keyword">else</span><br>        linkBefore(element, node(index));<br>&#125;<br></code></pre></div></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">checkPositionIndex</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (!isPositionIndex(index))<br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IndexOutOfBoundsException(outOfBoundsMsg(index));<br>&#125;<br><span class="hljs-comment">// 检查下标合法性 index ∈ [0, size]</span><br><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isPositionIndex</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;<br>    <span class="hljs-keyword">return</span> index &gt;= <span class="hljs-number">0</span> &amp;&amp; index &lt;= size;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="添加-addFirst-E-e"><a href="#添加-addFirst-E-e" class="headerlink" title="添加 addFirst(E e)"></a>添加 addFirst(E e)</h4><ul>
<li>[插入元素到链表头](#插入元素到链表头 linkFirst(E e))</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">addFirst</span><span class="hljs-params">(E e)</span> </span>&#123;<br>    linkFirst(e);<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="添加-addLast-E-e"><a href="#添加-addLast-E-e" class="headerlink" title="添加 addLast(E e)"></a>添加 addLast(E e)</h4><ul>
<li>[插入元素到链表尾](#尾插法添加元素 linkLast(E e))</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">addLast</span><span class="hljs-params">(E e)</span> </span>&#123;<br>    linkLast(e);<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="删除-remove-Object-o-1"><a href="#删除-remove-Object-o-1" class="headerlink" title="删除 remove(Object o)"></a>删除 remove(Object o)</h4><ul>
<li><p>删除指定元素的<strong>第一个</strong>匹配项</p>
<ul>
<li><strong>if</strong> 待删除元素为 <code>null</code><ul>
<li>从头查找第一个 <code>null</code>，从链表[断开节点](#删除节点 unlink(Node<E> x))</li>
</ul>
</li>
<li><strong>else</strong> 待删除元素不空<ul>
<li>从头查找第一个值符合的元素，从链表[断开节点](#删除节点 unlink(Node<E> x))</li>
</ul>
</li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">remove</span><span class="hljs-params">(Object o)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (o == <span class="hljs-keyword">null</span>) &#123;<br>        <span class="hljs-keyword">for</span> (Node&lt;E&gt; x = first; x != <span class="hljs-keyword">null</span>; x = x.next) &#123;<br>            <span class="hljs-keyword">if</span> (x.item == <span class="hljs-keyword">null</span>) &#123;<br>                unlink(x);<br>                <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;<br>            &#125;<br>        &#125;<br>    &#125; <span class="hljs-keyword">else</span> &#123;<br>        <span class="hljs-keyword">for</span> (Node&lt;E&gt; x = first; x != <span class="hljs-keyword">null</span>; x = x.next) &#123;<br>            <span class="hljs-keyword">if</span> (o.equals(x.item)) &#123;<br>                unlink(x);<br>                <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;<br>            &#125;<br>        &#125;<br>    &#125;<br>    <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="尾插法添加元素-linkLast-E-e"><a href="#尾插法添加元素-linkLast-E-e" class="headerlink" title="尾插法添加元素 linkLast(E e)"></a>尾插法添加元素 linkLast(E e)</h4><ul>
<li><code>l</code> 指针指向链表尾部，用于标记<strong>原链表尾</strong></li>
<li>根据 <code>Node(Node&lt;E&gt; prev, E element, Node&lt;E&gt; next)</code> 创建值为 <code>e</code>，前驱为 <code>l</code> 即 <code>last</code>，后继为 <code>null</code> 的节点，这么构造符合<strong>尾节点</strong>特点</li>
<li>链表尾指针移动到新链表尾</li>
<li><strong>if</strong> 原链表尾是 <code>null</code> <ul>
<li>说明「链表为空」，此时插入的为第一个节点，因此头指针也指向新节点</li>
</ul>
</li>
<li><strong>else</strong> 原链表不为 <code>null</code><ul>
<li>说明「链表不空」，尾插到链表上</li>
</ul>
</li>
<li><code>size</code> &amp; <code>modCount</code> 自增</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">linkLast</span><span class="hljs-params">(E e)</span> </span>&#123;<br>    <span class="hljs-keyword">final</span> Node&lt;E&gt; l = last;<br>    <span class="hljs-keyword">final</span> Node&lt;E&gt; newNode = <span class="hljs-keyword">new</span> Node&lt;&gt;(l, e, <span class="hljs-keyword">null</span>);<br>    last = newNode;<br>    <span class="hljs-keyword">if</span> (l == <span class="hljs-keyword">null</span>)<br>        first = newNode;<br>    <span class="hljs-keyword">else</span><br>        l.next = newNode;<br>    size++;<br>    modCount++;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="插入元素到非空节点之前-linkBefore-E-e-Node-succ"><a href="#插入元素到非空节点之前-linkBefore-E-e-Node-succ" class="headerlink" title="插入元素到非空节点之前 linkBefore(E e, Node succ)"></a>插入元素到非空节点之前 linkBefore(E e, Node<E> succ)</h4><ul>
<li>断言 <code>index</code>节点非空</li>
<li>获得 <code>index</code> 节点前驱 <code>pred</code> </li>
<li>创建节点，值为 <code>e</code>，前驱为 <code>pred</code>，后继为 <code>succ</code></li>
<li>后继连接上新节点</li>
<li><strong>if</strong> 前驱为空<ul>
<li>说明「插入位置在链表头」，头指针指向新节点</li>
</ul>
</li>
<li><strong>else</strong> 后继为空<ul>
<li>说明「插入位置在中间」，前驱指向新节点</li>
</ul>
</li>
<li><code>size</code> &amp; <code>modCount</code> 自增</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">linkBefore</span><span class="hljs-params">(E e, Node&lt;E&gt; succ)</span> </span>&#123;<br>    <span class="hljs-comment">// assert succ != null;</span><br>    <span class="hljs-keyword">final</span> Node&lt;E&gt; pred = succ.prev;<br>    <span class="hljs-keyword">final</span> Node&lt;E&gt; newNode = <span class="hljs-keyword">new</span> Node&lt;&gt;(pred, e, succ);<br>    succ.prev = newNode;<br>    <span class="hljs-keyword">if</span> (pred == <span class="hljs-keyword">null</span>)<br>        first = newNode;<br>    <span class="hljs-keyword">else</span><br>        pred.next = newNode;<br>    size++;<br>    modCount++;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="插入元素到链表头-linkFirst-E-e"><a href="#插入元素到链表头-linkFirst-E-e" class="headerlink" title="插入元素到链表头 linkFirst(E e)"></a>插入元素到链表头 linkFirst(E e)</h4><ul>
<li>获得头节点</li>
<li>创建节点，值为 <code>e</code>，前驱为 <code>null</code>，后继为 <code>f</code>，即旧头结点</li>
<li>头指针移到新节点</li>
<li><strong>if</strong> 旧头节点为空<ul>
<li>说明「链表为空」，尾指针指向新节点</li>
</ul>
</li>
<li><strong>else</strong> 旧头节点不空<ul>
<li>说明「链表不空」，连接 新节点&amp;旧头结点</li>
</ul>
</li>
<li><code>size</code> &amp; <code>modCount</code> 自增</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">linkFirst</span><span class="hljs-params">(E e)</span> </span>&#123;<br>    <span class="hljs-keyword">final</span> Node&lt;E&gt; f = first;<br>    <span class="hljs-keyword">final</span> Node&lt;E&gt; newNode = <span class="hljs-keyword">new</span> Node&lt;&gt;(<span class="hljs-keyword">null</span>, e, f);<br>    first = newNode;<br>    <span class="hljs-keyword">if</span> (f == <span class="hljs-keyword">null</span>)<br>        last = newNode;<br>    <span class="hljs-keyword">else</span><br>        f.prev = newNode;<br>    size++;<br>    modCount++;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="删除节点-unlink-Node-x"><a href="#删除节点-unlink-Node-x" class="headerlink" title="删除节点 unlink(Node x)"></a>删除节点 unlink(Node<E> x)</h4><ul>
<li>断言 节点不空</li>
<li>获取 该节点 <code>element</code>、前驱 <code>prev</code> 和后继 <code>next</code></li>
<li><strong>if</strong> 前驱为空<ul>
<li>说明「该节点为头节点」，头指针直接指向后继</li>
</ul>
</li>
<li><strong>else</strong> 前驱不空<ul>
<li>说明「该节点非头节点」，前驱指向后继，再断「x 指向前驱」</li>
</ul>
</li>
<li>双向链表，后面的方向道理同上</li>
<li><code>size</code> 自减， <code>modCount</code> 自增，元素置空，返回删除的节点</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function">E <span class="hljs-title">unlink</span><span class="hljs-params">(Node&lt;E&gt; x)</span> </span>&#123;<br>    <span class="hljs-comment">// assert x != null;</span><br>    <span class="hljs-keyword">final</span> E element = x.item;<br>    <span class="hljs-keyword">final</span> Node&lt;E&gt; next = x.next;<br>    <span class="hljs-keyword">final</span> Node&lt;E&gt; prev = x.prev;<br><br>    <span class="hljs-keyword">if</span> (prev == <span class="hljs-keyword">null</span>) &#123;<br>        first = next;<br>    &#125; <span class="hljs-keyword">else</span> &#123;<br>        prev.next = next;<br>        x.prev = <span class="hljs-keyword">null</span>;<br>    &#125;<br><br>    <span class="hljs-keyword">if</span> (next == <span class="hljs-keyword">null</span>) &#123;<br>        last = prev;<br>    &#125; <span class="hljs-keyword">else</span> &#123;<br>        next.prev = prev;<br>        x.next = <span class="hljs-keyword">null</span>;<br>    &#125;<br><br>    x.item = <span class="hljs-keyword">null</span>;<br>    size--;<br>    modCount++;<br>    <span class="hljs-keyword">return</span> element;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="检索节点在链表的下标位置-node-int-index"><a href="#检索节点在链表的下标位置-node-int-index" class="headerlink" title="检索节点在链表的下标位置 node(int index)"></a>检索节点在链表的下标位置 node(int index)</h4><ul>
<li>断言 <code>index∈[0, size)</code></li>
<li><strong>if</strong> 下标在左半边<ul>
<li>从头向中间检索</li>
</ul>
</li>
<li><strong>else</strong> 下标在右半边<ul>
<li>从后向中间检索</li>
</ul>
</li>
</ul>
<p>📌二分思想，利用好双向链表，同时头尾节点都是固定的。</p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function">Node&lt;E&gt; <span class="hljs-title">node</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;<br>    <span class="hljs-comment">// assert isElementIndex(index);</span><br>    <span class="hljs-keyword">if</span> (index &lt; (size &gt;&gt; <span class="hljs-number">1</span>)) &#123;<br>        Node&lt;E&gt; x = first;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; index; i++)<br>            x = x.next;<br>        <span class="hljs-keyword">return</span> x;<br>    &#125; <span class="hljs-keyword">else</span> &#123;<br>        Node&lt;E&gt; x = last;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = size - <span class="hljs-number">1</span>; i &gt; index; i--)<br>            x = x.prev;<br>        <span class="hljs-keyword">return</span> x;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="获取元素四种方法的区别"><a href="#获取元素四种方法的区别" class="headerlink" title="获取元素四种方法的区别"></a>获取元素四种方法的区别</h4><p><code>getFirst()</code> &amp; <code>getLast()</code> &amp; <code>peekFirst()</code> &amp; <code>peekLast()</code> </p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">peekFirst</span><span class="hljs-params">()</span> </span>&#123;<br>    <span class="hljs-keyword">final</span> Node&lt;E&gt; f = first;<br>    <span class="hljs-keyword">return</span> (f == <span class="hljs-keyword">null</span>) ? <span class="hljs-keyword">null</span> : f.item;<br>&#125;<br><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">getFirst</span><span class="hljs-params">()</span> </span>&#123;<br>    <span class="hljs-keyword">final</span> Node&lt;E&gt; f = first;<br>    <span class="hljs-keyword">if</span> (f == <span class="hljs-keyword">null</span>)<br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> NoSuchElementException();<br>    <span class="hljs-keyword">return</span> f.item;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>很明显，<code>peek</code> 类型的方法在空链表时会返回 <code>null</code>，<code>get</code> 类型则<strong>抛出异常</strong> <code>NoSuchElementException</code> </li>
</ul>
<h4 id="LinkedList-作双端队列和栈的细节"><a href="#LinkedList-作双端队列和栈的细节" class="headerlink" title="LinkedList 作双端队列和栈的细节"></a>LinkedList 作双端队列和栈的细节</h4><p>因为 <code>LinkedList </code> 同时也实现了 <code>Deque</code> 接口，所以可以作为<strong>双端队列</strong>，自然也可以当做<strong>栈</strong>「一开一闭」。</p>
<ul>
<li>栈</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;<br>        Deque&lt;Integer&gt; stack = <span class="hljs-keyword">new</span> ArrayDeque&lt;Integer&gt;();<br>        stack.push(<span class="hljs-number">1</span>);<br>        stack.push(<span class="hljs-number">2</span>);<br>        stack.push(<span class="hljs-number">3</span>);<br>        System.out.println(stack);<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<blockquote>
<p>[3, 2, 1]</p>
</blockquote>
<ul>
<li>队列</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;<br>        Deque&lt;Integer&gt; queue = <span class="hljs-keyword">new</span> ArrayDeque&lt;Integer&gt;();<br>        queue.offer(<span class="hljs-number">1</span>);<br>        queue.offer(<span class="hljs-number">2</span>);<br>        queue.offer(<span class="hljs-number">3</span>);<br>        System.out.println(queue);<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<blockquote>
<p>[1, 2, 3]</p>
</blockquote>
<p>既然可以同时作队列和栈，引发思考，同为 <code>peek()</code> 获得「栈顶」| 「队头」元素，那么猜测<strong>队列首部</strong>和<strong>栈顶开口</strong>是<strong>同个方向</strong>的。</p>
<ul>
<li>查看 <code>Deque</code> 的 <code>peek()</code> 官方注释</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">/**</span><br><span class="hljs-comment"> * Retrieves, but does not remove, the head of the queue represented by</span><br><span class="hljs-comment"> * this deque (in other words, the first element of this deque), or</span><br><span class="hljs-comment"> * returns &#123;<span class="hljs-doctag">@code</span> null&#125; if this deque is empty.</span><br><span class="hljs-comment"> *</span><br><span class="hljs-comment"> * &lt;p&gt;This method is equivalent to &#123;<span class="hljs-doctag">@link</span> #peekFirst()&#125;.</span><br><span class="hljs-comment"> *</span><br><span class="hljs-comment"> * <span class="hljs-doctag">@return</span> the head of the queue represented by this deque, or</span><br><span class="hljs-comment"> *         &#123;<span class="hljs-doctag">@code</span> null&#125; if this deque is empty</span><br><span class="hljs-comment"> */</span><br><span class="hljs-function">E <span class="hljs-title">peek</span><span class="hljs-params">()</span></span>;<br></code></pre></div></td></tr></table></figure>
<p><code>peek()</code> 返回 deque 队列头， 如果双端队列为空，则返回 <code>null</code></p>
<ul>
<li>查看 <code>LinkedList</code> 实现的 <code>peek()</code></li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">peek</span><span class="hljs-params">()</span> </span>&#123;<br>    <span class="hljs-keyword">final</span> Node&lt;E&gt; f = first;<br>    <span class="hljs-keyword">return</span> (f == <span class="hljs-keyword">null</span>) ? <span class="hljs-keyword">null</span> : f.item;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<p>获取左侧链表首部</p>
<ul>
<li>查看 <code>ArrayDeque</code> 实现的 <code>peek()</code></li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">peek</span><span class="hljs-params">()</span> </span>&#123;<br>    <span class="hljs-keyword">return</span> peekFirst();<br>&#125;<br></code></pre></div></td></tr></table></figure>
<p>获取队列首部</p>
<p>📌结论：官方定义的左边（First）是<code>栈首</code>，<code>队列头</code>。由此才能实现一个方法达到相同的<strong>peek</strong> 效果。</p>
<h2 id="🔗Reference："><a href="#🔗Reference：" class="headerlink" title="🔗Reference："></a>🔗<strong>Reference：</strong></h2><blockquote>
</blockquote>
<section class="footnotes"><div class="footnote-list"><ol><li><span id="fn:1" class="footnote-text"><span><a target="_blank" rel="noopener" href="https://stackoverflow.com/questions/35756277/why-the-maximum-array-size-of-arraylist-is-integer-max-value-8">Why the maximum array size of ArrayList is Integer.MAX_VALUE - 8?</a>
<blockquote>
</blockquote>
<a href="#fnref:1" rev="footnote" class="footnote-backref"> ↩</a></span></span></li><li><span id="fn:2" class="footnote-text"><span><a target="_blank" rel="noopener" href="https://developer.ibm.com/articles/j-codetoheap/#:~:text=those%20128%20bits.-,Anatomy%20of%20a%20Java%20array%20object,-The%20shape%20and">Anatomy of a Java array object</a>
<blockquote>
</blockquote>
<a href="#fnref:2" rev="footnote" class="footnote-backref"> ↩</a></span></span></li><li><span id="fn:3" class="footnote-text"><span><a target="_blank" rel="noopener" href="https://developer.ibm.com/articles/j-codetoheap/#:~:text=the%20native%20heap.-,Anatomy%20of%20a%20Java%20object,-When%20your%20Java">Anatomy of a Java object</a>
<blockquote>
</blockquote>
<a href="#fnref:3" rev="footnote" class="footnote-backref"> ↩</a></span></span></li><li><span id="fn:4" class="footnote-text"><span><a target="_blank" rel="noopener" href="https://stackoverflow.com/questions/33147339/difference-between-if-a-b-0-and-if-a-b">[Difference between if (a - b &lt; 0) and if (a &lt; b)]</a>
<a href="#fnref:4" rev="footnote" class="footnote-backref"> ↩</a></span></span></li></ol></div></section>
            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/categories/JavaSE/">JavaSE</a>
                    
                  </div>
                
                
              </div>
              
                <p class="note note-warning">
                  
                    本博客所有文章除特别声明外，均采用 <a target="_blank" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！
                  
                </p>
              
              
                <div class="post-prevnext">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2021/08/16/JavaSE/Java%E5%B8%B8%E7%94%A8%E9%9B%86%E5%90%88%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90%20%E2%85%A1/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">Java常用集合源码分析 Ⅱ</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2021/06/02/JVM/JVM%E3%80%8CHotSpot%20VM%E3%80%8D/">
                        <span class="hidden-mobile">JVM「HotSpot VM」</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div class="toc-body" id="toc-body"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    

    
      <a id="scroll-top-button" href="#" role="button">
        <i class="iconfont icon-arrowup" aria-hidden="true"></i>
      </a>
    

    
      <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
    

    
  </main>

  <footer class="text-center mt-5 py-3">
  <div class="footer-content">
     © 2019-2021 
  </div>
  
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


  

  
</footer>


  <!-- SCRIPTS -->
  
  <script  src="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.css" />

  <script>
    NProgress.configure({"showSpinner":false,"trickleSpeed":100})
    NProgress.start()
    window.addEventListener('load', function() {
      NProgress.done();
    })
  </script>


<script  src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js" ></script>
<script  src="https://cdn.jsdelivr.net/npm/bootstrap@4.5.3/dist/js/bootstrap.min.js" ></script>
<script  src="/js/debouncer.js" ></script>
<script  src="/js/events.js" ></script>
<script  src="/js/plugins.js" ></script>

<!-- Plugins -->


  
    <script  src="/js/img-lazyload.js" ></script>
  



  



  <script  src="https://cdn.jsdelivr.net/npm/tocbot@4.12.0/dist/tocbot.min.js" ></script>



  <script  src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js" ></script>



  <script  src="https://cdn.jsdelivr.net/npm/anchor-js@4.3.0/anchor.min.js" ></script>



  <script defer src="https://cdn.jsdelivr.net/npm/clipboard@2.0.6/dist/clipboard.min.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>




  <script  src="https://cdn.jsdelivr.net/npm/typed.js@2.0.11/lib/typed.min.js" ></script>
  <script>
    (function (window, document) {
      var typing = Fluid.plugins.typing;
      var title = document.getElementById('subtitle').title;
      
      typing(title)
      
    })(window, document);
  </script>



  <script  src="/js/local-search.js" ></script>
  <script>
    (function () {
      var path = "/local-search.xml";
      $('#local-search-input').on('click', function() {
        searchFunc(path, 'local-search-input', 'local-search-result');
      });
      $('#modalSearch').on('shown.bs.modal', function() {
        $('#local-search-input').focus();
      });
    })()
  </script>





  

  
    <!-- MathJax -->
    <script>
      MathJax = {
        tex: {
          inlineMath: [['$', '$'], ['\\(', '\\)']]
        },
        options: {
          renderActions: {
            findScript: [10, doc => {
              document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
                const display = !!node.type.match(/; *mode=display/);
                const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
                const text = document.createTextNode('');
                node.parentNode.replaceChild(text, node);
                math.start = { node: text, delim: '', n: 0 };
                math.end = { node: text, delim: '', n: 0 };
                doc.math.push(math);
              });
            }, '', false],
            insertedScript: [200, () => {
              document.querySelectorAll('mjx-container').forEach(node => {
                let target = node.parentNode;
                if (target.nodeName.toLowerCase() === 'li') {
                  target.parentNode.classList.add('has-jax');
                }
              });
            }, '', false]
          }
        }
      };
    </script>

    <script async src="https://cdn.jsdelivr.net/npm/mathjax@3.1.2/es5/tex-svg.js" ></script>

  











<!-- 主题的启动项 保持在最底部 -->
<script  src="/js/boot.js" ></script>


</body>
</html>
